#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

void helper(vector<int> &array, int si, int ei) {
  if (si >= ei) {
    return;
  }

  int pivot = si;
  int l = si + 1;
  int r = ei;

  while (l <= r) {
    if (array[l] > array[pivot] && array[r] < array[pivot]) {
      swap(array[l], array[r]);
    }

    if (array[l] <= array[pivot]) {
      ++l;
    }

    if (array[r] >= array[pivot]) {
      --r;
    }
  }

  swap(array[r], array[pivot]);

  // r 位置成为了新的轴
  helper(array, si, r - 1); // 每一次向下递归的时候，传递的都是上一步已经排序好一个数字之后的新数组
  helper(array, r + 1, ei);
}

void quickSort(vector<int> &array) {
  helper(array, 0, array.size() - 1);
}

int main(int argc, char const *argv[])
{
  /* code */
  return 0;
}
